package com.algrithom.stack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

import com.common.constants.NumberConstants;
import com.util.CommonUtil;

/**
 * 单调栈 84 85 739 503 42 901 239 962
 *
 * @author think
 * @version 1.0.0
 * @since 2020/4/25
 */
public class Solution3 {
    
    public static void main(String[] args){
        int[] nums1 = {4,1,2};
        int[] nums2 = {1,3,4,2};
        System.out.println(Arrays.toString(nextGreaterElement1(nums1,nums2)));
        System.out.println(Arrays.toString(nextGreaterElement2(nums2)));
        System.out.println(nextGreaterElement3(156432));
    }
    
    public static int[] nextGreaterElement1(int[] nums1,int[] nums2){
        int[] result = new int[nums1.length];
        Arrays.fill(result,-1);
        Stack<Integer> stk = new Stack<>();
        Map<Integer,Integer> map = new HashMap<>(NumberConstants.ZERO);
        for (int value : nums2) {
            while (!stk.empty() && value > stk.peek()) {
                map.put(stk.peek(),value);
                stk.pop();
            }
            stk.push(value);
        }
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                result[i] = map.get(nums1[i]);
            }
        }
        return result;
    }
    
    public static int[] nextGreaterElement2(int[] nums){
        int size = nums.length;
        int[] result = new int[size];
        Stack<Integer> stk = new Stack<>();
        for (int index = NumberConstants.TWO * size - 1; index >= 0; index--) {
            while (!stk.empty() && nums[index % size] >= stk.peek()) {
                stk.pop();
            }
            result[index % size] = stk.isEmpty() ? -1 : stk.peek();
            stk.push(nums[index % size]);
        }
        return result;
    }
    
    /**
     * 下一个更大元素 III
     *
     * @param n 输入
     * @return 输出
     */
    public static int nextGreaterElement3(int n){
        char[] chars = String.valueOf(n).toCharArray();
        for (int i = chars.length - 1; i > 0; --i) {
            if (chars[i - 1] >= chars[i]) {
                continue;
            }
            --i;
            int j = i;
            while (j != chars.length - 1 && chars[j + 1] > chars[i]) {
                ++j;
            }
            CommonUtil.swap(chars,i,j);
            for (int k = i + 1; k <= i + (chars.length - 1 - i) / 2; ++k) {
                CommonUtil.swap(chars,k,chars.length + i - k);
            }
            return Integer.parseInt(new String(chars));
        }
        return -1;
    }
}
